package sorting;

import util.Tracer;
import collections.PriorityQueueMin;

public class SortedArrayMerger{
	public static void merge(int[] ... sortedArrays) throws Exception
	{
		PriorityQueueMin<SortedArrayNode> queue = new PriorityQueueMin<SortedArrayNode>();

		for(int i = 0, length = sortedArrays.length; i < length; i ++)
		{
			queue.insert(new SortedArrayNode(sortedArrays[i]));
		}
		
		while(queue.getAvailable() > 0)
		{
			SortedArrayNode node = queue.minimum();
			Tracer.trace(node.extractMin());
			
			if(node.getAvailable() > 0)
				queue.minHeapify(0);
			else
				queue.extractMin();
		}
	}
	
	public static void main(String[] args) throws Exception {
		merge(new int[]{1, 4, 7}, new int[]{2, 5, 8}, new int[]{3, 6, 9});
	}
}

class SortedArrayNode implements Comparable<SortedArrayNode>
{
	private int[] items;
	private int seeker;

	public SortedArrayNode(int[] items) {
		this.items = items;
	}
	
	public int minimum()
	{
		return items[seeker];
	}
	
	public int extractMin()
	{
		return items[seeker ++];
	}
	
	public int getAvailable()
	{
		return items.length - seeker;
	}

	@Override
	public int compareTo(SortedArrayNode o) {
		if(getAvailable() == 0)
			return -1;
		
		return minimum() - o.minimum();
	}
}